package treePath;

import util.TreeNode;

/**
 * @program: javase
 * @description: 同值路径长度
 * https://leetcode-cn.com/problems/binary-tree-paths/solution/yi-pian-wen-zhang-jie-jue-suo-you-er-cha-5f58/
 * @author: luolidong
 * @create: 2021-07-02 17:01
 * @version: 1.0
 */
public class SomePathSum {
    int ans = 0;

    public int longestUnivaluePath(TreeNode root) {
        if (root == null) return 0;
        longest(root);
        return ans;

    }

    public int longest(TreeNode root) {
        if (root == null) return 0;
        int leftLen = longest(root.left);
        int rightLen = longest(root.right);
        //这里判断与左右节点是否相等，相当于返回最大相等个数
        int curLeftLen = 0;
        int curRightLen = 0;
        if (root.left != null && root.left.val == root.val) {
            curLeftLen += leftLen;
        }
        if (root.right != null && root.right.val == root.val) {
            curRightLen += rightLen;
        }
        ans = Math.max(ans, curLeftLen + curRightLen);
        return Math.max(curRightLen, curLeftLen)+1;
    }

    public static void main(String[] args) {
        int i = new SomePathSum().longestUnivaluePath(TreeNode.build());
        System.out.println(i);
    }
}
